package com.ntd.study.algorithm.sort.impl;

import cn.hutool.core.util.ArrayUtil;
import com.ntd.study.algorithm.sort.Sort;

import java.util.function.BiFunction;

/**
 * 堆排序
 *
 * @author liuwenju
 * @date 2021/4/30 17:22
 */
public class SortHeap<T> implements Sort<T> {

    private BiFunction<T, T, Boolean> sort;

    @Override
    public T[] sort(T[] arrays, BiFunction<T, T, Boolean> sort) {
        this.sort = sort;
        // 对 arr 进行拷贝，不改变参数内容
        int len = arrays.length;

        buildMaxHeap(arrays, len);

        for (int i = len - 1; i > 0; i--) {
            ArrayUtil.swap(arrays, 0, i);
            len--;
            heapify(arrays, 0, len);
        }
        return arrays;
    }

    private void buildMaxHeap(T[] arr, int len) {
        for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
            heapify(arr, i, len);
        }
    }

    private void heapify(T[] arr, int i, int len) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;

        if (left < len && sort.apply(arr[left], arr[largest])) {
            largest = left;
        }

        if (right < len && sort.apply(arr[right], arr[largest])) {
            largest = right;
        }

        if (largest != i) {
            ArrayUtil.swap(arr, i, largest);
            heapify(arr, largest, len);
        }
    }
}
